package base

import "traning/algorithm/utility"

func NewSmallHeap(cap int) *MySmallHeap {
	return &MySmallHeap{arr: make([]int, cap), limit: cap}
}

type MySmallHeap struct {
	arr []int
	size int
	limit int
}

func (h *MySmallHeap) Push(val int) {
	if h.size == h.limit {
		panic(any("heap is full !!!"))
	}
	h.arr[h.size] = val
	h.insert(h.size)
	h.size++
}

func (h *MySmallHeap) Pop () int {
	if h.size == 0 {panic(any("heap is empty"))}
	utility.Swap(h.arr, 0, h.size-1)
	h.size--
	h.heapify(0)
	return h.arr[h.size]
}

func  (h *MySmallHeap) Size () int {
	return h.size
}

func (h *MySmallHeap) heapify(index int) {
	left := 2*index + 1
	for left < h.size {
		small := left
		if h.arr[left] > h.arr[left+1] && left+1 < h.size {
			small = left+1
		}
		if h.arr[index] < h.arr[small] {
			break
		}
		utility.Swap(h.arr,index, small)
	}
}

func (h *MySmallHeap) insert(index int) {
	parent := (index-1)/1
	for index > 0 {
		if h.arr[parent] > h.arr[index] {
			utility.Swap(h.arr, parent, index)
		} else {
			break
		}
		index = parent
		parent = (index-1)/1
	}
}




